package 剑指offer;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/25 11:18 星期四
 */
public class _06_从尾到头打印链表 {

    //确定数组长度后，倒序插入
    public int[] reversePrintQuick(ListNode head){
        if (head == null){
            return new int[0];
        }

        int num = 0;
        ListNode n = head;
        while (n!=null){
            num ++;
            n = n.next;
        }

        int[] retArr = new int[num];
        while (num > 0){
            retArr[--num] = head.val;
            head = head.next;
        }
        return retArr;
    }

    /**
     * 使用栈的思想，和栈的API，实现了链表倒序
     * > 2022/08/25 14:29:46
     * 解答成功:
     * 	执行耗时:1 ms,击败了67.35% 的Java用户
     * 	内存消耗:41.8 MB,击败了84.43% 的Java用户
     * @param head
     * @return
     */
    public int[] reversePrint(ListNode head) {
        if (head == null) {
            //为空，返回0长度数组
            return new int[0];
        }

        //创建栈
        Stack<Integer> stack = new Stack<>();
        int index = 0;

        //结点不为空，计数器+1，头结点右移
        while (head != null) {
            stack.push(head.val);
            index++;
            head = head.next;
        }

        //new一个新数组，作为返回
        int[] arr = new int[index];
        for (int i = 0; i < index; i++) {
            //弹栈+记录
            arr[i] = stack.pop();
        }

        return arr;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
